Corelab Seminar
2009-2010
Eirini Pogiatzi (NTUA)
On the hardness of being truthful (Christos Papadimitriou, Michael Schapira, Yaron Singer).
Abstract (from the original publication). The central problem in computational mechanism design
is the tension between incentive compatibility and
computational efficiency. We establish the first significant
approximability gap between algorithms that are
both truthful and computationally-efficient, and algorithms
that only achieve one of these two desiderata.
This is shown in the context of a novel mechanism design
problem which we call the COMBINATORIAL PUBLIC
PROJECT PROBLEM (CPPP). CPPP is an abstraction
of many common mechanism design situations, ranging
from elections of kibbutz committees to network design.
Our result is actually made up of two complementary
results – one in the communication-complexity model
and one in the computational-complexity model. Both
these hardness results heavily rely on a combinatorial
characterization of truthful algorithms for our problem.
Our computational-complexity result is one of the first
impossibility results connecting mechanism design to
complexity theory; its novel proof technique involves an
application of the Sauer-Shelah Lemma and may be of
wider applicability, both within and without mechanism
design."